#include "strategy.h"

void BubbleSortStrategy::sort(std::vector<int>& v)
{
    int len = v.size();
    for(int i = 1;i < len; i++)
    {
        bool changed = false;
        for(int j = 0;j < len - i; j++)
        {
            if(v[j] > v[j + 1])
            {
                std::swap(v[j],v[j + 1]);
                changed = true;
            }
        }
        show(v);
        if(!changed)
            break;
    }
}

void SelectionSortSrategy::sort(std::vector<int> & v)
{
    int len = v.size();
    for(int i = 0;i < len -1;i++)
    {
        int minValue = i;
        for(int j = i + 1;j < len ;j++)
        {
            if(v[j] < v[minValue])
                minValue = j;
        }
        if(i != minValue)
            std::swap(v[i],v[minValue]);
    }
}

void InsertSortStrategy::sort(std::vector<int>& v)
{
    int len = v.size();
    for(int i = 1;i < len;i++)
    {
        int temp = v[i];
        int j = 0;
        for(j = i - 1;j >= 0;j--)
        {
            if(v[j] > temp)
            {
                v[j+1]  = v[j];
            }
            else{
                break;
            }
        }
        v[j+1] = temp;
    }
}

void ShellSortStrategy::sort(std::vector<int> & v)
{
    int len = v.size();
    int step = v.size() / 2;
    for(;step >=1 ;step /= 2)
    {
        for(int i = step;i < len;i+= step)
        {
            int temp = v[i];
            int j = 0;
            for(j = i - step;j >= 0;j-= step)
            {
                if(v[j] > temp)
                {
                    v[j + step]  = v[j];
                }
                else{
                    break;
                }
            }
            v[j+step] = temp;
        }
    }
}

void MergeSortStrategy::merge(std::vector<int>& v,int left,int mid,int right)
{
    std::vector<int> tempLeft(v.begin() + left,v.begin() + mid + 1);
    std::vector<int> tempRight(v.begin()+ mid + 1,v.begin()+ right + 1);
    int i = 0,j =  0;
    int k = left;
    while(i < tempLeft.size() && j <tempRight.size())
    {
        while(i < tempLeft.size() && tempLeft[i] <= tempRight[j])
        {
            v[k++] = tempLeft[i++];
        }

        while(j < tempRight.size() && tempRight[j] < tempLeft[i])
        {
            v[k++] = tempRight[j++];
        }

    }

    while(i < tempLeft.size())
    {
        v[k++] = tempLeft[i++];
    }

    while(j < tempRight.size())
    {
        v[k++] = tempRight[j++];
    }
}

void MergeSortStrategy::mergeSort(std::vector<int>& v,int left,int right)
{
    if(left < right)
    {
        int mid = (right + left) / 2;
        this->mergeSort(v,left,mid);
        this->mergeSort(v,mid+1,right);
        this->merge(v,left,mid,right);
    }  
}

void MergeSortStrategy::sort(std::vector<int> & v)
{
    this->mergeSort(v,0,v.size()-1);
}

int QuickSortStrategy::privot(std::vector<int> &v,int left, int right)
{
    int base = v[left];
    int i = left,j = right;
    while(i < j)
    {
        while(i < j && v[j] >= base)
        {
            j--;
        }
        while(i < j && v[i] <= base)
        {
            i++;
        }
        std::swap(v[i],v[j]);
    }
    if(i != left)
        std::swap(v[i],v[left]);
    return i;       
    
}

void QuickSortStrategy::quickSort(std::vector<int> &v, int left, int right)
{
    if(left < right)
    {
        int pvt = this->privot(v,left,right);
        this->quickSort(v,left,pvt - 1);
        this->quickSort(v,pvt + 1,right);
    }
    
}

void QuickSortStrategy::sort(std::vector<int> &v)
{
    this->quickSort(v,0,v.size() - 1);
}

void HeapSortStrategy::heapify(std::vector<int> &v, int index, int n)
{
    
    int largest = index;
    int left = 2 * largest + 1;
    int right = 2 * largest + 2;
    if(left < n && v[left] > v[largest])
        largest = left;
    if(right < n && v[right] > v[largest])
        largest = right;
    if(largest != index)
    {
        std::swap(v[index],v[largest]);
        heapify(v,largest,n);
    }
}

void HeapSortStrategy::sort(std::vector<int> &v)
{
    int n = v.size();
    for(int i = n / 2 - 1;i >= 0;i--)
    {
        heapify(v,i,n);
    }
    for(int j = n-1;j >= 0;j--)
    {
        std::swap(v[0],v[j]);
        heapify(v,0,j);
    }
}

void Sorter::setStrategy(SortStrategy *strategy)
{
    m_strategy = strategy;
}

SortStrategy *Sorter::getStrategy()
{
    return m_strategy;
}

void Sorter::sort(std::vector<int> &v)
{
    m_strategy->sort(v);

}

void Sorter::show(std::vector<int> & v)
{
    m_strategy->show(v);
}